package 中等.二分查找;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的
 * 子序列的单词个数 。
 * 字符串的 子序列 是从原始字符串中生成的新字符串，可以从
 * 中删去一些字符(可以是none)，而不改变其余字符的相对顺序。
 * 例如， “ace” 是 “abcde” 的子序列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-matching-subsequences
 */
public class 匹配子序列的单词数_792 {

    public static void main(String[] args) {

        System.out.println(numMatchingSubseq2("abcde", new String[]{"bb"}));

    }

    /**
     * 常规双指针（超时）
     *
     * @param s
     * @param words
     * @return
     */
    public static int numMatchingSubseq(String s, String[] words) {
        int count = 0;
        char[] sArr = s.toCharArray();
        for (String word : words) {
            int wIdx = 0, sIdx = 0;
            while (wIdx < word.length() && sIdx < s.length()) {
                while (sIdx < s.length() && sArr[sIdx] != word.charAt(wIdx)) {
                    sIdx++;
                }
                if (sIdx < s.length() && sArr[sIdx] == word.charAt(wIdx)) {
                    wIdx++;
                    sIdx++;
                } else {
                    break;
                }
            }
            if (wIdx == word.length()) {
                count++;
            }
        }
        return count;
    }

    /**
     * 双指针+预处理+二分查找
     * 对于每个 word[i] ，我们想要找到 s 中最小索引等于它的 s[j]
     * 可以先将 s 中每个字符的索引分开存储，预处理成26个数组，
     * j 为大于左边界（上一个匹配位置的右边一个位置）的对应字符的最小索引
     *
     * @param s
     * @param words
     * @return
     */
    public static int numMatchingSubseq2(String s, String[] words) {
        int count = 0;
        List<Integer>[] pos = new List[26];
        for (int i = 0; i < pos.length; i++) {
            pos[i] = new ArrayList<>();
        }
        for (int i = 0; i < s.length(); i++) {
            pos[s.charAt(i) - 'a'].add(i);
        }

        for (String word : words) {
            int sIdx = 0, wIdx = 0;
            while (wIdx < word.length()) {
                int nextLeft = next(pos[word.charAt(wIdx) - 'a'], sIdx);
                if (nextLeft == -1) {
                    break;
                }
                sIdx = nextLeft + 1;
                wIdx++;
            }
            if (wIdx == word.length()) {
                count++;
            }
        }

        return count;
    }

    // pos 中 >= sIdx 的最小数
    private static int next(List<Integer> pos, int sIdx) {
        int ans = -1;
        int l = 0, r = pos.size() - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (pos.get(mid) == sIdx) {
                return sIdx;
            } else if (pos.get(mid) > sIdx) {
                ans = pos.get(mid);
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return ans;
    }

}
